package DP.路径;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    3干中↓单 中的 ‘限制’好有用  (注意不要跳着走
 */
public class 只可左下_最小路径_64 {
    @Test
    public void test() {
        int[][] a = {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(minPathSum(a));
    }

    int[][] g;
    public int minPathSum(int[][] G) {
        g=G; int n1=G.length,n2=G[0].length;
        int i=n1-1,j=n2-1;
        return back(i,j);
    }

    private int back(int i, int j) {
        can(String.format("%s",g[i][j]));
        if(i==0 && j==0){
            r(g[0][0]+"");
            return g[0][0];
        }

        int lf = j-1>=0? back(i,j-1):9999;
        int up = i-1>=0? back(i-1,j):9999;

        r(g[i][j] + Math.max(up,lf)+";");
        return  g[i][j] + Math.min(up,lf);
    }
}
